package solution.search;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.junit.Assert;
import org.junit.Test;

import data.Data;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class SumToANumber {

	Set<Integer> hs = null;

	public int getCounts(int number) throws Exception {
		if (hs == null)
			throw new Exception("not initialized.");

		int sum = 0;
		for (Integer i : hs) {
			int j = number - i;
			if (j < i) {
				continue;
			}
			if (hs.contains(j)) {
				// System.out.println(Math.sqrt(i) + ", " + Math.sqrt(j));
				sum++;
			}
		}
		return sum;
	}

	public int getCounts2(int number) throws Exception {
		int sum = 0;
		for (int i = 0; i <= Math.sqrt(number) + 1; i++) {
			int i2 = i * i;
			int j2 = number - i2;
			if (j2 < i2) {
				break;
			}

			int j = (int) Math.sqrt(j2);
			if (j2 == j * j) {
				sum++;
			}
		}
		return sum;
	}

	public void init(int max) {
		hs = new HashSet<Integer>((int) (Math.sqrt(max) / 0.7));
		for (int i = 0; i < Math.sqrt(max); i++) {
			hs.add(i * i);
		}
	}

	@Test
	public void test() throws Exception {
		List<List<String>> data = Data.getDataAsList("facebook2.txt");
		init(2147483647);

		for (List<String> line : data) {
			int num = Integer.valueOf(Integer.valueOf(line.get(0)));
			int r1 = getCounts(num);
			int r2 = getCounts2(num);
			System.out.println(r1);

			Assert.assertEquals(r1, r2);
		}
	}
}
